<?php
/**
 * @title 43. 字符串相乘 - 迭代+反转
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param String $num1
     * @param String $num2
     * @return String
     */
    function multiply($num1, $num2) {
        /**
         * @since 2020-08-13 特殊情况
         */
        if($num1 == "0" OR $num2 == "0"){
            return "0";
        } else {}

        /**
         * @since 2020-08-13 长度
         */
        $len1 = strlen($num1);
        $len2 = strlen($num2);

        /**
         * @since 2020-08-13 结果集
         */
        $len = $len1+$len2;
        $result = array_fill(0, $len, 0);

        /**
         * @since 2020-08-13 逐位相乘
         */
        $k1 = 0;
        for ($i=$len1-1; $i>=0; $i--){
            $n = $num1[$i];

            $k2 = $k1;
            for ($j=$len2-1; $j>=0; $j--){
                $result[$k2] = $result[$k2]+$num2[$j]*$n;
                $k2++;
            }

            $k1++;
        }
        // return $result;

        /**
         * @since 2020-08-13 进位操作
         */
        $add = 0;
        for($i=0; $i<$len; $i++){
            $n = $result[$i]+$add;
            if($n>=10){
                $result[$i] = $n%10;
                $add = intval($n/10);
            } else {
                $result[$i] = $n;
                $add = 0;
            }
            // echo "n={$n}, result[{$i}]=", $result[$i], ", add={$add}", PHP_EOL;
        }
        // return $result;

        /**
         * @since 2020-08-13 去掉高位0
         */
        if($result[$len-1] == "0"){
            unset($result[$len-1]);
        } else {}

        /**
         * @return
         */
        return strrev(implode("", $result));
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.21_7.php
 */
$datas = [
    // ["2", "3"],
    // ["45", "67"],
    ["9", "9"],
    // ["123", "456"], // 56088
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->multiply($data[0], $data[1]);
    // $result = $obj->find("6888", "49200");
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
